package com.cn.why.film.filmindex.face.binary_tree;

import java.util.LinkedList;

/**
 * 二叉树的三种遍历方法（递归：先序遍历、中序遍历、后序遍历）
 */
public class TwoTreeNode<T> {
    /**
     * 先序创建二叉树，返回根节点
     * @param treeData
     * @return
     */
    public TreeNode<T> creatBinaryPre(LinkedList<T> treeData){
        TreeNode<T> root = null;//定义根节点
        T data = treeData.removeFirst();
        if(data!=null){
            root=new TreeNode<T>(data, null, null);
            root.left=creatBinaryPre(treeData);
            root.right=creatBinaryPre(treeData);
        }
        return root;//返回根节点
    }

    /**
     * 先序遍历（递归）
     * @param root
     */
    public void PrintBinaryTreePreRecur(TreeNode<T> root){
        if(root!=null){
            //开始的时间
            System.out.println(root.data);
            PrintBinaryTreePreRecur(root.left);
            PrintBinaryTreePreRecur(root.right);
        }
    }

    /**
     * 中序遍历（递归）
     */
    public void PrintBinaryTreeMidRecur(TreeNode<T> root){
        if(root!=null){
            PrintBinaryTreeMidRecur(root.left);
            System.out.println(root.data);
            PrintBinaryTreeMidRecur(root.right);
        }
    }

    /**
     * 后序遍历（递归）
     * @param root
     */
    public void PrintBinaryTreeBacRecur(TreeNode<T> root){
        if(root!=null){
            PrintBinaryTreeBacRecur(root.left);
            PrintBinaryTreeBacRecur(root.right);
            System.out.println(root.data);
        }
    }

    /*
     * 测试二叉树的  创建、遍历
     * 二叉树结构如下
     *            A
     *       B         C
     *    D     E   F     G
     *  H   I        J
     */
    public static void main(String[] args) {
        TwoTreeNode<Character> tTwoTreeNode = new TwoTreeNode<>();
        //输入ABDH##I##E##CF#J##G##（#用null代替）
        LinkedList<Character> tree = new LinkedList<>();
        tree.add('A');tree.add('B');tree.add('D');
        tree.add('H');tree.add(null);tree.add(null);
        tree.add('I');tree.add(null);tree.add(null);
        tree.add('E');tree.add(null);tree.add(null);
        tree.add('C');tree.add('F');tree.add(null);
        tree.add('J');tree.add(null);tree.add(null);
        tree.add('G');tree.add(null);tree.add(null);

        TreeNode<Character> root = tTwoTreeNode.creatBinaryPre(tree);
        //先序遍历
        tTwoTreeNode.PrintBinaryTreePreRecur(root);
        System.out.println("***");
        //中序遍历
        tTwoTreeNode.PrintBinaryTreeMidRecur(root);
        System.out.println("***");
        //后序遍历
        tTwoTreeNode.PrintBinaryTreeBacRecur(root);

    }
}
